package com.gxc.string;

/**
 * 请注意区分子串和子序列的不同，给定两个字符串str1和str2，求两个字符串的最长公共子串。
 *
 * 动态规划空间压缩的技巧讲解
 *
 * 子串：原序列中必须连续的一段
 * 子序列：原序列中可以不连续的一段
 *
 * 解法：
 * dp：
 *  dp[i][j] 代表以  str1 以i, str2 以 j 结尾的最大公共子串，
 *  如果 str[i]==str[j] ，则 dp[i][j] = dp[i-1][j-1]+1,
 *  如果 str[i]!=str[j]， 则 dp[i][j] = 0;
 */
public class LongestCommonSubstring {

    public static void main(String[] args) {
        String x = "abcadf";
        String y = "acbad";
        System.out.println(process(x, y));
        System.out.println(process2(x, y));
        System.out.println(process3(x, y));
        System.out.println(processStr(x, y));
    }

    /**
     * 最长公共子串的长度
     * @param str1
     * @param str2
     * @return
     */
    public static int process(String str1, String str2) {
        int[][] dp = new int[str1.length()][str2.length()];
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        //base case
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            if (chars1[i] == chars2[0]) {
                dp[i][0] = 1;
                max = 1;
            }
        }
        for (int i = 0; i < str2.length(); i++) {
            if (chars1[0] == chars2[i]) {
                dp[0][i] = 1;
                max = 1;
            }
        }


        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (chars1[i] == chars2[j]) dp[i][j] = dp[i-1][j-1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }

    /**
     * 最长公共子串的长度
     * 空间压缩  从二维数据压缩成一维数组
     * dp[i][j] = dp[i-1][j-1]+1
     * 根据公式，可得当前位置的值依赖左上位置的值与别的位置没关系，所以用一个一维数组记录即可
     * @param str1
     * @param str2
     * @return
     */
    public static int process2(String str1, String str2) {
        int[] dp = new int[str2.length()+1];
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        int pre = 0;
        int cur = 0;
        int max = 0;
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                cur = dp[j];
                if (j == 1) {
                    pre = 0;
                }
                if (chars1[i-1] == chars2[j-1]) {
                    dp[j] = pre+1;
                } else {
                    //因为是一个数组维持，所以要重置数据
                    dp[j] = 0;
                }
                pre = cur;
                max = Math.max(max, dp[j]);
            }
        }

        return max;
    }

    /**
     * 最长公共子串的长度
     * 空间压缩  从二维数据压缩成 几个变量
     * https://blog.csdn.net/qq_45865991/article/details/123754618
     * dp[i][j] = dp[i-1][j-1]+1
     * 根据公式，可得当前位置的值依赖左上位置的值与别的位置没关系，所以用几个变量即可（按斜线计算）
     *
     * 从右上角顶点先向左滑，滑动到左上角顶点时，再向下滑动，滑到左下角顶点为止
     * @param str1
     * @param str2
     * @return
     */
    public static int process3(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int l1 = str1.length();
        int l2 = str2.length();

        int row = 0;
        int col = str2.length()-1;
        int max = 0;

        while (row < l1 || col>0) {
            int i = row;
            int j = col;
            int length = 0;
            //斜线计算最大长度
            while (i<l1 && j<l2) {
                if (chars1[i] == chars2[j]) {
                    length++;
                } else {
                    length = 0;
                }
                i++;
                j++;
                max = Math.max(max, length);
            }

            //从右上角顶点先向左滑，滑动到左上角顶点时，再向下滑动，滑到左下角顶点为止
            if (col == 0) {
                row++;
            } else {
                col--;
            }
        }

        return max;
    }

    /**
     * 最长公共子串的字符串
     * @param str1
     * @param str2
     * @return
     */
    public static String processStr(String str1, String str2) {
        int[][] dp = new int[str1.length()][str2.length()];
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        //base case
        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            if (chars1[i] == chars2[0]) {
                dp[i][0] = 1;
                max = 1;
            }
        }
        for (int i = 0; i < str2.length(); i++) {
            if (chars1[0] == chars2[i]) {
                dp[0][i] = 1;
                max = 1;
            }
        }

        //记录下最大max时的坐标，str1(loc-max+1, loc+1)  就是最长公共子串
        int loc = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (chars1[i] == chars2[j]) dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    loc = i;
                }
            }
        }

        return str1.substring(loc-max+1, loc+1);
    }


}
